Computer systems often use data structures to track and manage access to resources. Such data structures need to be efficient in terms of indexing operations, insert/delete operations, and search operations. An ordered sequence is a common data structure to store ordered data of fixed size. Indexing an ordered sequence of N items is simple, with a time complexity of O(1). The time complexity of a lookup operation for the ordered sequence is O(log N), which is also efficient. However, an update of the ordered sequence (insertion or deletion) has a complexity of O(N) since each element in the sequence ranked below the insertion/deletion point has to be shifted to in order maintain the order. Thus, the time complexity for insertion/deletion in an ordered sequence is poor.
A binary search tree (BTree) of N items has a time complexity of O(log N) for lookup, which is also efficient. Furthermore, an insertion/deletion update in a BTree is also efficient, with a time complexity of O(log N). However, indexing the BTree has a poor time complexity of O(N). The BTree also requires at least two additional pointers for each data item, and so the space overhead is relatively high.
As the number of resources being managed in a cloud computing environment is increasing by several orders of magnitude, improved data structures that can provide high performance in indexing operations, insert/delete operations, and search operations would be desirable.